package 抽象数据类型;


import java.util.*;
import java.util.Queue;

public class HuffmanTreeNode extends BinTreeNode {
    private int weight; //权值
    private String coding = "";  //编码

    //构造方法
    public HuffmanTreeNode(int weigth) {
        this(weigth, null);
    }

    public HuffmanTreeNode(int weight, Comparable object) {
        super(new Node(object));
        this.weight = weight;
    }

    //改写父类方法


    @Override
    public HuffmanTreeNode getParent() {
        return (HuffmanTreeNode) super.getParent();
    }

    @Override
    public HuffmanTreeNode getLChild() {
        return (HuffmanTreeNode) super.getLChild();
    }

    @Override
    public HuffmanTreeNode getRChild() {
        return (HuffmanTreeNode) super.getRChild();
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    public String getCoding() {
        return coding;
    }

    public void setCoding(String coding) {
        this.coding = coding;
    }

    //通过结点数组生成Huffman树
    private static HuffmanTreeNode buildHufffmanTree(HuffmanTreeNode[] nodes) {
        int n = nodes.length;
        if (n < 2) {
            return nodes[0];
        }
        ArrayList arrayList = new ArrayList<>();
        arrayList.addAll(Arrays.asList(nodes));


        for (int i = 1; i < n; i++) {
            Collections.sort(arrayList);
            HuffmanTreeNode min1 = (HuffmanTreeNode) arrayList.remove(arrayList.size() - 1);
            HuffmanTreeNode min2 = (HuffmanTreeNode) arrayList.remove(arrayList.size() - 1);
            HuffmanTreeNode newRoot = new HuffmanTreeNode(min1.getWeight() + min2.getWeight());
            newRoot.setLChild(min1);
            newRoot.setRChild(min2);
            arrayList.add(newRoot);
        }
        return (HuffmanTreeNode) arrayList.get(0);
    }


    public int compareTo(HuffmanTreeNode o) {
        //如果o1.data的int值大于o2返回-1，
        return this.getWeight() > o.getWeight() ? -1 : 1;
    }

    private static void print(HuffmanTreeNode root) {
        Queue<HuffmanTreeNode> queue = new LinkedList<HuffmanTreeNode>();
        queue.add(root);
        while (!queue.isEmpty()) {
            HuffmanTreeNode node = queue.remove();
            System.out.println(node.getWeight());
            if (node.getLChild() != null) {
                queue.add(node.getLChild());
            }
            if (node.getRChild() != null) {
                queue.add(node.getRChild());
            }
        }

    }

    public static void main(String[] args) {
        HuffmanTreeNode[] nodes = new HuffmanTreeNode[6];
        int[] arr = new int[]{7, 4, 2, 9, 15, 5};
        for (int i = 0; i < arr.length; i++) {
            nodes[i] = new HuffmanTreeNode(arr[i]);

        }
        print(buildHufffmanTree(nodes));
    }

    private static void generateHuffmanCode(HuffmanTreeNode root) {
        if (root == null) {
            return;
        }
        if (root.hasParent()) {
            if (root.isLChild()) {
                root.setCoding(root.getParent() + "0");
            } else {
                root.setCoding(root.getParent() + "1");
            }
        }
        generateHuffmanCode(root.getLChild());
        generateHuffmanCode(root.getRChild());
    }


}
